
/**
 * 
 * @author zhangjinrui
 * 第k大的数
 * 本题采用作死的快排思路来实现
 */
public class Five {
	
	public int kthLargestElement(int k, int[] nums) {
		return getK(k,nums);
    }
	
	/**
	 * 
	 * @param k
	 * @param nums 需要保证nums的长度不为0，同时k小于等于nums.length
	 * @return
	 */
	public int getK(int k, int[] nums){
		if(nums.length == 1){
			return nums[0];
		}
		
		int split = nums[0];
		int l = 0;
		int r = nums.length - 1;
		
		while(l < r){
			while(r > l && nums[r] >= split){
				r --;
			}
			nums[l] = nums[r];
			
			while(l < r && nums[l] < split){
				l ++;
			}
			
			nums[r] = nums[l];
		}
		nums[l] = split;
		if(k == (nums.length - l)){
			return nums[l];
		}
		if(k > (nums.length - l)){
			int[] lnums = new int[l];
			for(int i = 0 ; i < l ; i ++){
				lnums[i] = nums[i];
			}
			return getK(k - (nums.length - l), lnums);
		}else{
			int len = nums.length - l - 1;
			int[] rnums = new int[len];
			for(int i = 0 ; i < len; i++){
				rnums[i] = nums[l+i+1];
			}
			return getK(k,rnums);
		}
	}
	
	public static void main(String args[]){
		int num[] = new int[]{10,23,4,100,6,7,10};
		System.out.println(new Five().kthLargestElement(2, num));
	}
}
